home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7752 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.7 KB
  1. Path: po.CWRU.Edu!mab22
  2. From: mab22@po.CWRU.Edu (Michael A. Balfour)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: unique id for a string
  5. Date: 28 Feb 1996 18:56:06 GMT
  6. Organization: Case Western Reserve University, Cleveland, OH (USA)
  7. Message-ID: <4h28g6$p66@madeline.INS.CWRU.Edu>
  8. References: <1996Feb16.175601.114182@kuhub.cc.ukans.edu> <3129dd39.961626@news.iquest.net> <4gfpveINNe68@keats.ugrad.cs.ubc.ca> <4gih8a$b62@madeline.INS.CWRU.Edu> <4gsh3hINNf3b@keats.ugrad.cs.ubc.ca>
  9. Reply-To: mab22@po.CWRU.Edu (Michael A. Balfour)
  10. NNTP-Posting-Host: kanga.ins.cwru.edu
  11.  
  12.  
  13. In a previous article, c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku) says:
  14.  
  15. >In article <4gih8a$b62@madeline.INS.CWRU.Edu>,
  16. >Michael A. Balfour <mab22@po.CWRU.Edu> wrote:
  17. > >
  18. > >Actually, it's not *that* difficult to find.  Try running gperf from GNU
  19. > >or reading the paper cited in my previous post in this subject.  The
  20. > >results in the paper claim to be able to find a perfect hash function
  21. > >for 262,144 18-character words in 16.087 seconds on a Sun Sparc 2.
  22. > >Doesn't sound that difficult to me.  :)
  23. > >
  24. > >>One way to get a unique mapping is to simply assign increasing numbers to the
  25. > >>200,000+ words, and use a hashing technique to quickly look up a word given its
  26. > >>integer tag, and look up the tag given the word. With the proper
  27. > >>represenatation, both operations can be done in "constant time".
  28. > >
  29. > >Once again, using a perfect minimal hash function will provide an easy
  30. > >method for accomplishing this.
  31. >
  32. >Definitely. But that assumes that the dictionary is not open to new members.
  33. >Otherwise you have to recompute the hashing function each time you add a
  34. >member. Does the paper discuss such ``loose ends''?
  35.  
  36. There's no mention of how to handle adding new members, but you're
  37. certainly correct.  You would want to generate a new hashing function
  38. each time you updated the dictionary.  Of course, the way I'm using
  39. this algorithm in my own code is to dynamically create the hash function
  40. at runtime after reading in the desired list of words.  So off-line
  41. updates to the dictionary wouldn't affect my code in the least.
  42.  
  43. >
  44. >I am probably going to have a look at it, since perfect hashing functions are
  45. >interesting things. :)
  46.  
  47. Once again, I heartily recommend this technique.  I've had the chance to
  48. try running it now, and it works like magic!  The paper can be found at
  49. ftp.cs.uq.edu.au in /pub/TECHREPORTS/departments/TR0242.ps.Z (I think)
  50. and the source code is in the same directory in the file
  51. perfes_10.tar.Z.  Happy hunting!
  52.  
  53. Mike Balfour
  54. -- 
  55. ----------------------------------+--------------------------------
  56. Mike Balfour, Partner             | BS/MS Graduate - ECMP
  57. Overload Engineering              | Case Western Reserve University
  58. "New Ideas for a Brighter Future" | Cleveland, OH
  59.